// <copyright file="PriorityQueueB.cs" company="Gustavo Franco">
// Copyright (c) 2006 All Right Reserved
// </copyright>
// <author>Gustavo Franco</author>
// <email>gustavo_franco@hotmail.com</email>
// <date>2006</date>
// <summary>A custom queue that is organized based on priority.</summary>

// THIS CODE AND INFORMATION IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY
// KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND/OR FITNESS FOR A PARTICULAR
// PURPOSE. IT CAN BE DISTRIBUTED FREE OF CHARGE AS LONG AS THIS HEADER
// REMAINS UNCHANGED.

// Email:  gustavo_franco@hotmail.com

// Copyright (C) 2006 Franco, Gustavo

// Work done by Robert Tenney on this library: PathFinder, is based off of the previous work
// done by: Franco, Gustavo.

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace TenneySoftware.Engine.Algorithms.Pathfinder {
    /// <summary>
    /// A custom queue that is organized based on priority.
    /// </summary>
    /// <typeparam name="T">The first generic type parameter.</typeparam>
    [Author("Franco, Gustavo")]
    public class PriorityQueueB<T> : IPriorityQueueCustom<T> {
        #region Variables Declaration
        /// <summary>
        /// Collection for the inner list.
        /// </summary>
        private InnerListCollection innerList = new InnerListCollection();

        /// <summary>
        /// Comparer used for comparison.
        /// </summary>
        private IComparer<T> comparer;
        #endregion

        #region Contructors
        /// <summary>
        /// Initializes a new instance of the PriorityQueueB class.
        /// </summary>
        public PriorityQueueB() {
            this.Comparer = Comparer<T>.Default;
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueueB class.
        /// </summary>
        /// <param name="comparer">The comparer to use for comparisons.</param>
        public PriorityQueueB(IComparer<T> comparer) {
            this.Comparer = comparer;
        }

        /// <summary>
        /// Initializes a new instance of the PriorityQueueB class.
        /// </summary>
        /// <param name="comparer">The comparer to use for comparisons.</param>
        /// <param name="capacity">The initial capacity to set the queue to.</param>
        public PriorityQueueB(IComparer<T> comparer, int capacity) {
            this.Comparer = comparer;
            this.InnerList.Capacity = capacity;
        }
        #endregion

        #region Properties
        /// <summary>
        /// Gets the total number of items in the queue.
        /// </summary>
        /// <value>
        /// The total number of items in the queue.
        /// </value>
        public int Count {
            get {
                return this.InnerList.Count;
            }
        }
        
        /// <summary>
        /// Gets the InnerListCollection.
        /// </summary>
        /// <value>
        /// The InnerListCollection.
        /// </value>
        protected InnerListCollection InnerList {
            get {
                return this.innerList;
            }
        }
        
        /// <summary>
        /// Gets or sets the comparer.
        /// </summary>
        /// <value>
        /// The comparer.
        /// </value>
        protected IComparer<T> Comparer {
            get {
                return this.comparer;
            }
            
            set {
                this.comparer = value;
            }
        }

        /// <summary>
        /// Gets or sets an item in the list from it's index.
        /// </summary>
        /// <param name="index">The index of the item.</param>
        /// <value>
        /// An item in the list from it's index.
        /// </value>
        public T this[int index] {
            get {
                return this.InnerList[index];
            }
            
            set {
                this.InnerList[index] = value;
                this.Update(index);
            }
        }
        #endregion
        
        #region Methods
        /// <summary>
        /// Push an object onto the priority queue.
        /// </summary>
        /// <param name="item">The new object.</param>
        /// <returns>The index in the list where the object is now. This will change when objects are taken from or put onto the PQ.</returns>
        public int Push(T item) {
            int p = this.InnerList.Count, p2;
            this.InnerList.Add(item); // E[p] = O
            do {
                if (p == 0) {
                    break;
                }
                
                p2 = (p - 1) / 2;
                if (this.OnCompare(p, p2) < 0) {
                    this.SwitchElements(p, p2);
                    p = p2;
                } else {
                    break;
                }
            } while (true);
            return p;
        }

        /// <summary>
        /// Get the smallest object and remove it.
        /// </summary>
        /// <returns>The smallest object.</returns>
        public T Pop() {
            T result = this.InnerList[0];
            int p = 0, p1, p2, pn;
            this.InnerList[0] = this.InnerList[this.InnerList.Count - 1];
            this.InnerList.RemoveAt(this.InnerList.Count - 1);
            do {
                pn = p;
                p1 = (2 * p) + 1;
                p2 = (2 * p) + 2;
                if (this.InnerList.Count > p1 && this.OnCompare(p, p1) > 0) { // links kleiner
                    p = p1;
                }
                
                if (this.InnerList.Count > p2 && this.OnCompare(p, p2) > 0) { // rechts noch kleiner
                    p = p2;
                }
                
                if (p == pn) {
                    break;
                }
                
                this.SwitchElements(p, pn);
            } while (true);

            return result;
        }

        /// <summary>
        /// Notify the PQ that the object at position i has changed
        /// and the PQ needs to restore order.
        /// Since you dont have access to any indexes (except by using the
        /// explicit IList.this) you should not call this function without knowing exactly
        /// what you do.
        /// </summary>
        /// <param name="i">The index of the changed object.</param>
        public void Update(int i) {
            int p = i, pn;
            int p1, p2;
            do {	// aufsteigen
                if (p == 0) {
                    break;
                }
                
                p2 = (p - 1) / 2;
                if (this.OnCompare(p, p2) < 0) {
                    this.SwitchElements(p, p2);
                    p = p2;
                } else {
                    break;
                }
            } while (true);
            if (p < i) {
                return;
            }
            
            do {   // absteigen
                pn = p;
                p1 = (2 * p) + 1;
                p2 = (2 * p) + 2;
                if (this.InnerList.Count > p1 && this.OnCompare(p, p1) > 0) { // links kleiner
                    p = p1;
                }
                
                if (this.InnerList.Count > p2 && this.OnCompare(p, p2) > 0) { // rechts noch kleiner
                    p = p2;
                }
                
                if (p == pn) {
                    break;
                }
                
                this.SwitchElements(p, pn);
            } while (true);
        }

        /// <summary>
        /// Get the smallest object without removing it.
        /// </summary>
        /// <returns>The smallest object.</returns>
        public T Peek() {
            if (this.InnerList.Count > 0) {
                return this.InnerList[0];
            }
            
        return default(T);
        }

        /// <summary>
        /// Clear the queue.
        /// </summary>
        public void Clear() {
            this.InnerList.Clear();
        }

        /// <summary>
        /// Remove an item from the queue.
        /// </summary>
        /// <param name="item">Item to remove.</param>
        public void RemoveLocation(T item) {
            int index = -1;
            for (int i = 0; i < this.InnerList.Count; i++) {
                if (this.Comparer.Compare(this.InnerList[i], item) == 0) {
                    index = i;
                }
            }

            if (index != -1) {
                this.InnerList.RemoveAt(index);
            }
        }
        
        /// <summary>
        /// Switch two elements within the queue.
        /// </summary>
        /// <param name="i">First element to switch.</param>
        /// <param name="j">Second element to switch.</param>
        protected void SwitchElements(int i, int j) {
            T h = this.InnerList[i];
            this.InnerList[i] = this.InnerList[j];
            this.InnerList[j] = h;
        }

        /// <summary>
        /// Compare two items within the queue.
        /// </summary>
        /// <param name="i">First item to compare.</param>
        /// <param name="j">Second item to compare.</param>
        /// <returns>Value less than Zero if i is less then j, Zero if they are the same, or a value higher than Zero if i is greater than j.</returns>
        protected virtual int OnCompare(int i, int j) {
            return this.Comparer.Compare(this.InnerList[i], this.InnerList[j]);
        }
        #endregion

        /// <summary>
        /// Provides a collection of inner items.
        /// </summary>
        protected internal class InnerListCollection : Collection<T> {
            /// <summary>
            /// Initializes a new instance of the InnerListCollection class.
            /// </summary>
            public InnerListCollection() : base(new List<T>()) {
            }

            /// <summary>
            /// Gets or sets the capacity of the collection.
            /// </summary>
            /// <value>
            /// The capacity of the collection.
            /// </value>
            public int Capacity {
                get {
                    return (Items as List<T>).Capacity;
                }

                set {
                    (Items as List<T>).Capacity = value;
                }
            }
        }
    }
}